In order to perform a specific operation or describe an operation process for acquiring a desired result in a computer, a user needs to prepare and execute a program with a “programming language”.
Before executing a program written in a computer language, the program to be executed needs be converted into a command defined in a computer system and in this case, a compiler performs a conversion process.
The compiler accepts the program to be executed and generates another type of program with the same purpose as an output. During such a process, the compiler may find an error of the accepted program and output a semantic error message.
The compiler checks which words are included in a source program. Herein, a semantic word is called a token. Consequently, the first operation to be performed to translate the source program into a object program is to identify which token is used in the source program. In the compiler, the identification is called lexical analysis.
Second, which component among components of a sentence these words fit into need to be checked. In other words, while viewing grammar, it is checked whether the tokens are grammatically correct and the compiler calls the checking syntax analysis. In the compiler, the checking is called syntax analysis.
The third operation is to check a semantic of the word, that is, perform semantic analysis. However, since a formal language does not have a semantic, a type is mainly checked in such a process. Code optimization for reducing an execution time of a code created by the semantic analysis or reducing a memory is performed and last, the object program is created by considering characteristics of an object machine.
There are many methods to describe a logical structure of the compiler, but the logical structure is mainly divided into a front end and a rear end to be described. The front end as an independent part of the object machine analyzes a source program regardless of the object machine and creates an intermediate code and the rear end as a part dependent on the object machine translates the intermediate code created at the front end into an object code for a specific machine.
In more detail, the compiler operates by each step (translating one representation of the source program to another representation of the source program in a computer) that translates the source program from one representation to another representation. A couple of steps in the compiler called a pass and one pass means that an output is generated by one scanning. Each step of the compiler is divided into two passes of the front end and the rear end, which results in a two-pass compiler.
The compiler usually uses a binary tree to represent a concatenated single operation that guarantees associate laws in a syntax analysis process. In this case, a tree may not be balanceably created and a skew problem occurs. The tree is referred to as a skewed tree. The skewed tree has a problem in that the skewed tree increases a stack memory usage and increases a compile time.